package com.niuke;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * 61. 二叉树遍历
 * https://zhuanlan.zhihu.com/p/641747890 (根据二叉树后序遍历和中序遍历，输出二叉树的层序遍历)
 * https://blog.csdn.net/qq_34143141/article/details/131667954 (二叉树遍历，输出二叉树的中序遍历结果)
 */
public class NiukeMoni61nan {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");

        Queue<String[]> queue = new LinkedList<>(); // 队列，先进先出
        queue.offer(input);

        List<Character> ans = new ArrayList<>();

        while (queue.size() > 0) {
            String[] curr = queue.poll();
            String houXu = curr[0];
            String zhongXu = curr[1];
            dfs(houXu, zhongXu, queue, ans);
        }

        System.out.println(Arrays.toString(ans.toArray()));

        // 第二题的代码
        getMidList("a{b{d,e{g,h{,i}}},c{f}}");

    }

    public static void dfs(String houXu, String zhongXu, Queue<String[]> queue,
                           List<Character> ans) {
        // 后序遍历的最后一个元素就是根
        char root = houXu.charAt(houXu.length() - 1);
        ans.add(root);

        // 在中序遍历中找到根的位置 rootIdx，那么该位置左边就是左子树，右边就是右子树
        int rootIndex = zhongXu.indexOf(root);

        // 左子树 因为是从0开始的
        int leftLen = rootIndex;
        int rightLen = houXu.length() - 1 - rootIndex;
        if (leftLen > 0) {
            String nextHouXu = houXu.substring(0, leftLen);
            String nextZhongXu = zhongXu.substring(0, leftLen);
            queue.offer(new String[]{nextHouXu, nextZhongXu});
        }

        if (rightLen > 0) {
            String nextHouXu = houXu.substring(leftLen, leftLen + rightLen);
            String nextZhongXu = zhongXu.substring(leftLen + 1);
            queue.offer(new String[]{nextHouXu, nextZhongXu});
        }

    }

    // a{b{d,e{g,h{,i}}},c{f}}
    public static void getMidList(String input) {
        Stack<Node> nodes = new Stack<>();
        Node preNode = null;
        for (int i = 0; i < input.length(); i++) {
            char curr = input.charAt(i);
            if (curr == '{') {
                Node node = new Node(input.charAt(i - 1));
                nodes.push(node);
            }
            if (curr == ',') {
                Node node = nodes.peek();
                Node left = null;
                if (input.charAt(i - 1) != '{') {
                    if (preNode != null) {
                        left = preNode;
                        preNode = null;
                    } else {
                        left = new Node(input.charAt(i - 1));
                    }
                }
                node.left = left;
            }

            if (curr == '}') {
                Node node = nodes.peek();
                if (input.charAt(i - 1) != ',' && input.charAt(i - 2) == '{') { // 再往前也不是逗号，改为设置左节点
                    node.left = new Node(input.charAt(i - 1));
                } else {
                    Node right = null;
                    if (input.charAt(i - 1) != ',') {
                        if (preNode != null) {
                            right = preNode;
                        } else {
                            right = new Node(input.charAt(i - 1));
                        }
                    }
                    node.right = right;
                }

                if (nodes.size() > 1) { // 防止最后剩下的根节点也被pop
                    preNode = nodes.pop();
                }
            }
        }

        inorderTraversal(nodes.pop());
        System.out.println("");
    }

    public static class Node {
        char val;
        Node left;
        Node right;

        Node(char val) {
            this.val = val;
        }
    }

    // 中序遍历
    public static void inorderTraversal(Node root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    }

}
